package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/6/13 23:30
 */
public class OddEvenList_328 {

    public ListNode oddEvenList(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode odd = head, even = head.next;

        // 哑结点起到固化的作用
        ListNode dummy1 = new ListNode(-1), dummy2 = new ListNode(-1);
        dummy1.next = odd;
        dummy2.next = even;

        while (even != null) {
            ListNode temp1 = odd, temp2 = even;
            odd = odd.next.next;
            even = even.next.next;
            temp1.next = odd;
            temp2.next = even;
        }

        odd.next = dummy2.next;
        return dummy1.next;
    }


}
